//做不出
//
// 随机取数pivot --> 排序 --> 返回索引 --> 看索引大于还是小于第k --> 然后在向k靠近（小于k向小的逼近排序，反之向大的逼近）

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int arr[] = {7, 3, 9, 1, 5, 2, 8}; // 示例数组
int n = sizeof(arr) / sizeof(arr[0]);

// 交换两个元素
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 分区函数：以pivot为界，左侧元素 <= pivot，右侧元素 > pivot
// 返回pivot在数组中的最终位置（即它是第i小的元素，i从1开始）
int partition(int start, int end) {
    // 随机选择pivot（优化最坏情况）
    int pivot_idx = start + rand() % (end - start + 1);
    swap(&arr[pivot_idx], &arr[end]); // 将pivot移到末尾

    int pivot = arr[end];
    int i = start - 1; // i是小于等于pivot区域的边界

    for (int j = start; j < end; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]); // 将当前元素加入小于等于pivot的区域
        }
    }
    swap(&arr[i + 1], &arr[end]); // 将pivot放到正确位置
    return i + 1; // 返回pivot的索引（0-based），对应的排名是i+2（1-based）
}

// 查找[start, end]区间内第k小的元素（k是1-based）
int order_statistic(int start, int end, int k) {
    if (start == end) {
        return arr[start]; // 区间只有一个元素，直接返回
    }

    // 分区后，pivot的索引是p（0-based）
    int p = partition(start, end);
    // pivot在区间[start, end]中的排名是（p - start + 1）（1-based）
    int rank = p - start + 1;

    if (k == rank) {
        return arr[p]; // 找到第k小的元素
    } else if (k < rank) {
        // 第k小的元素在左半部分
        return order_statistic(start, p - 1, k);
    } else {
        // 第k小的元素在右半部分，需调整k的值（减去左半部分的元素个数）
        return order_statistic(p + 1, end, k - rank);
    }
}

int main() {
    srand(time(0)); // 初始化随机数种子
    int k = 3; // 查找第3小的元素
    int result = order_statistic(0, n - 1, k);
    printf("数组中第%d小的元素是：%d\n", k, result); // 示例输出：3（对应数组[1,2,3,5,7,8,9]）
    return 0;
}
